import java.util.HashSet;
import java.util.Set;

class Solution {
    public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
    public ListNode reverseList(ListNode head) {
        ListNode curr=head;
        ListNode prev=null;
        while(curr!=null){
            ListNode next=curr.next;
            curr.next=prev;
            prev=curr;
            curr=next;
        }
        return prev;
    }
    public ListNode detectCycle(ListNode head) {
        ListNode pos=head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while(pos!=null){
            if(visited.contains(pos)){
                return pos;
            }else{
                visited.add(pos);
            }pos = pos.next;
        }return null;
    }
}